package create.randomizedSet;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * @Time 2020/1/4
 * @author 王光浩
 * @Need 创建一个数据结构，该数据结构要求插入和删除元素的平均时间复杂度为O（1），另外需要一个从集合中随机
 *       获取元素的方法，该方法获取每一个数据的概率要一致。
 *       思路：HashMap+ArrayList。HashMap提供常数时间的insert和remove，但是不能够提供常数时间的getRandom，
 *             ArrayList能够提供常数时间的insert和getRandom，但是不能提供常数时间的remove，所以在HashMap中
 *             提供元素在ArrayList中下标的索引，在ArrayList中存储对应元素值，当remove时获取要删除元素的索引，将
 *             其与ArrayList中最后一个元素进行交换（别忘记更新HashMap中想要的value值），在getRandom时，根据ArrayList
 *             长度，获取一个随机数，然后获取对应随机数所在下标作为返回值。
 */
public class OthersMethod {
	private Map<Integer,Integer> hashMap;
	private Random rand;
	private List<Integer> arrayList;
	
    /** Initialize your data structure here. */
    public OthersMethod() {
        hashMap=new HashMap<Integer,Integer>();
        rand=new Random();
        arrayList=new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
       if(!hashMap.containsKey(val)) {
    	   hashMap.put(val, arrayList.size());
    	   arrayList.add(val);
    	   return true;
       }
       return false;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(hashMap.containsKey(val)) {
        	//删除val，并且更新最后一个元素的下标
        	hashMap.put(arrayList.get(arrayList.size()-1), hashMap.get(val)); 
        	arrayList.set(hashMap.get(val), arrayList.get(arrayList.size()-1));
        	//元素移除
        	arrayList.remove(arrayList.size()-1);       
        	hashMap.remove(val);
        	return true;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int count=rand.nextInt(arrayList.size());
        return arrayList.get(count);
    }

}
